package advance.x000.acw_89;


import java.util.Scanner;

/**
 * 求 a 的 b 次方对 p 取模的值。
 * <p>
 * 输入格式
 * 三个整数 a,b,p ,在同一行用空格隔开。
 * <p>
 * 输出格式
 * 输出一个整数，表示a^b mod p的值。
 * <p>
 * 数据范围
 * 0≤a,b≤109
 * 1≤p≤109
 * 输入样例：
 * 3 2 7
 * 输出样例：
 * 2
 */
public class Main {

    public static void main(String[] args) {
        Main solution = new Main();
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        int p = scanner.nextInt();
        int ans = solution.power(a, b, p);
        System.out.println(ans);
    }

    public int power(int a, int b, int p) {
        //  快速幂
        // 一种基本的方法就是简单的按照a^b的方法累乘，但是这样计算的时间复杂度是O(n)的，如果b很大的话，会超时
        // 一种优化方法是，按照b的二进制来累乘，计算出b的二进制表达，然后将其分解为2的幂相加的形式，然后计算出a^(2^n)，
        // 这样可以将时间复杂度降低到log(N)

        // 这里必须使用long类型，不然对于某些比较大的数会溢出
        long ans = 1 % p;
        long k=a;
        for (; b != 0; b >>= 1) {
            if ((b & 1) == 1) {
                ans = (ans * k )% p;
            }
            k = (k * k) % p;
        }
        return (int) ans;
    }
}
